package fun.coding.leetcode;

public class PalindromeNumber {

	public static void main(String[] args) {
		PalindromeNumber ins = new PalindromeNumber();
		System.out.println(ins.isPalindrome(-121));
		System.out.println(ins.isPalindrome(121));
		System.out.println(ins.isPalindrome(-2147447412));
		System.out.println(ins.isPalindrome(1000021));
	}

	/**
	 * Determine whether an integer is a palindrome. Do this without extra space.
	 * 1) for integer problem, always think about +, -, 0
	 * 2) convert int to string will work, but uses extra space
	 */
	public boolean isPalindrome(int x) {
		if (x < 0) return false; // Based on this question, negative is not palindrome
		if (x == 0) return true;

		int div = (int)Math.pow(10, getNumberOfDigit(x) - 1);

		while (x > 0) {
			int left = x / div;
			int right = x % 10;

			if (left != right) return false;

			x = (x - left * div) / 10;
			// Note: this is clever than my initial thought, we use div to keep track of getting the digit so that 1000021 case is solved
			div = div / 100;
		}
		return true;
	}

	private int getNumberOfDigit(int x) {
		int count = 0;
		while (x != 0) {
			x = x / 10;
			count++;
		}
		return count;
	}

	// if you reverse a palindrome, it is the same, but what happens if overflow??
	public boolean isPalindromeReverseIntegerMethod(int x) {
		if(x < 0) {
			return false;
		}
		return x == reverse(x);    
	}

	public int reverse(int x) {
		int rst = 0;
		while(x != 0) {
			rst = rst * 10 + x % 10;
			x = x / 10;
		}
		return rst;
	}

	private int y;
	// http://yucoding.blogspot.com/2013/04/leetcode-question-62-palindrome-number.html
	public boolean isPalindromeRecursion(int x) {
		if (x < 0) return false;
		y = x;
		return helper(x);
	}
	
	private boolean helper(int x) {
		if (x == 0) return true;
		
		if (helper(x/10)) {
			if (x % 10 != y % 10) {
				return false;
			} else {
				y = y / 10;
				return true;
			}
		}
		
		return false;
	}
}
